class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        qsort(0,nums.size()-1,nums);
        return nums[nums.size()-k];
    }

    void qsort(int l, int r, vector<int>& nums)
{
    if (l >= r) return; // 如果左边界大于等于右边界，说明子数组长度为0或1，无需排序
    int left = l - 1, i = l, right = r + 1; // 初始化三个指针
    int key = getRandom(l, r, nums); // 随机选取基准值
    while (i < right) // 循环对数组进行分区
    {
        if (nums[i] < key) // 当前元素小于基准值
        {
            swap(nums[++left], nums[i++]); // 将元素交换到左边区域，并移动指针
        }
        else if (nums[i] > key) // 当前元素大于基准值
        {
            swap(nums[i], nums[--right]); // 将元素交换到右边区域，并移动指针
        }
        else // 当前元素等于基准值
        {
            i++; // 直接跳过，保持元素在中间区域
        }
    }
    qsort(l, left, nums); // 对左边区域递归排序
    qsort(right, r, nums); // 对右边区域递归排序
}
 
    int getRandom(int left,int right,vector<int>& nums)
    {
        int r = rand();
        return nums[r%(right-left+1)+left];
    }
 
};